package day06;

import java.sql.SQLOutput;
import java.util.Arrays;

public class arrtest {
    public static void main(String[] args) {
        int []arr={5,7,3,1,6,9,4,2,8,0};
        System.out.println(Arrays.toString(arr));
        System.out.println();
        //1.bubble
//        for (int i = 0; i <arr.length-1 ; i++) {
//            for (int j = 0; j <arr.length-1-i ; j++) {
//                if (arr[j]>arr[j+1]){
//                    int t=arr[j];
//                    arr[j]=arr[j+1];
//                    arr[j+1]=t;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
        //2.
//        for (int i = 0; i < arr.length-1; i++) {
//            for (int j = i+1; j <arr.length ; j++) {
//                if (arr[i]>arr[j]){
//                    int t=arr[i];
//                    arr[i]=arr[j];
//                    arr[j]=t;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
        //3.
//        for (int i = 0; i <arr.length-1 ; i++) {
//            for (int j = i+1; j >0 ; j--) {
//                if (arr[j-1]>arr[j]){
//                    int t=arr[j-1];
//                    arr[j-1]=arr[j];
//                    arr[j]=t;
//                }else {
//                    break;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
        //4.
//        for (int gap = arr.length/2; gap >0 ; gap/=2) {
//            for (int i = gap; i <arr.length ; i++) {
//                for (int j = i-gap; j >=0 ; j-=gap) {
//                    if (arr[j+gap]<arr[j]){
//                        int t=arr[j];
//                        arr[j]=arr[j+gap];
//                        arr[j+gap]=t;
//                    }else {
//                        break;
//                    }
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
        //5.
//        System.out.println(Arrays.toString(Merge(arr,0,arr.length-1)));
        //6.
//        Quick(arr,0,arr.length-1);
//        System.out.println(Arrays.toString(arr));


    }
    public static int[] Merge(int[] arr,int start,int end){
        int mid=start+(end-start)/2;
        if (start==end){
            return new int[]{arr[start]};
        }
        int[] leftArray=Merge(arr,start,mid);
        int[] rightArray=Merge(arr,mid+1,end);
        int l=0,r=0,n=0;
        int[] newArray=new int[leftArray.length+rightArray.length];
        while (l<leftArray.length&&r<rightArray.length){
            newArray[n++]=leftArray[l]<=rightArray[r]?leftArray[l++]:rightArray[r++];
        }
        while (l<leftArray.length){
            newArray[n++]=leftArray[l++];
        }
        while (r<rightArray.length){
            newArray[n++]=rightArray[r++];
        }
        return newArray;
    }
    private static void Quick(int[]arr,int start,int end){
        int x=start,y=end;
        int pivot=arr[end];
        while (x<y){
            while(x<y&&arr[y]>pivot){
                y--;
            }
            while (x<y&&arr[x]<pivot){
                x++;
            }
            if (x<y&&arr[x]==arr[y]){
                x++;
            }else {
                int t=arr[x];
                arr[x]=arr[y];
                arr[y]=t;
            }
            if (x-1>start){
                Quick(arr,start,x-1);
            }
            if (y+1<end){
                Quick(arr,y+1,end);
            }
        }
    }
}
